Optimization by Pravin Varaiya

Author:Pravin Varaiya
Language: eng
Format: epub
Tags: Optimization,

Figure 5.8: h(x k ) is a feasible direction.

Call h(x) an optimum solution of (5.46) and let ho(x) = ip(x)(h(x)) be the minimum value attained. (Note that by Exercise 1 of 4.5.1 (5.46) can be solved as an LP.)

The following algorithm is due to Topkis and Veinott [1967]. Step 1. Find x° G $7, set k = 0, and go to Step 2.

Step 2. Solve (5.46) for x = x k and obtain ho(x k ), h(x k ). If ho(x k ) = 0, stop, otherwise go to Step 3.

Step 3. Compute an optimum solution fi(x k ) to the one-dimensional problem,

Maximize fo(x k + /j,h(x k )) ,

subject to (x k + fih(x k )) £ 1!, |i > 0 ,

and go to Step 4.

Step 4. Set x k+1 = x k + p,(x k )h(x k ), set k = k + 1 and return to Step 2.

The performance of the algorithm is summarized below. Theorem 1: Suppose that the set

n(z°) = {x\x e n, /oO) > /o(x 0 )}

is compact, and has a non-empty interior, which is dense in tt(x°). Let x* be any limit point of the sequence x°,x l ,... ,x k ,..., generated by the algorithm. Then the Kuhn-Tucker conditions are satisfied at x*.

For a proof of this result and for more efficient algorithms the reader is referred to (Polak [1971]). Remark: If ho(x k ) < 0 in Step 2, then the direction h{x k ) satisfies fo x {x k )h(x k ) > 0, and fi(x k ) + f ix (x K )h(x k ) < 0, 1 < i < m. For this reason h(x k ) is called a (desirable) feasible direction. (See Figure 5.8.)

5.5. APPENDIX 73

5.5 Appendix

The proofs of Lemmas 4,7 of Section 2 are based on the following extremely important theorem (see Rockafeller [1970]).

Separation theorem for convex sets. Let F, G be convex subsets of R n such that the relative interiors of F, G are disjoint. Then there exists A G R n , A / 0, and 9 G R such that

A's < 9 for all geG A'/ > 9 for all / G F .

Proof of Lemma 4: Since M is stable at 6 there exists if such that

Af (6) - Af (S) < K\b - b\ for all b G 5 . (5.47)

In i? 1+m consider the sets

F = {(r, 6)|6 e R m , r> K\b-b\} , G = {(r, b)\b G F, r < M{b) - M(S)} .

It is easy to check that F, G are convex, and (5.47) implies that F n G = <p. Hence, there exist (Aq, • • •, A m ) / 0, and 6 such that

A 0 r + J2 x ibi < 0 for (r, 6) G G ,

i=l m

X 0 r + ^ XA > 6 for (r, b) G F .

(5.48)

i=l

From the definition of F, and the fact that (Ao, ■ ■ ■, A m ) / 0, it can be verified that (5.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.